from PositionalList import *


class FavoritesList:
    """维护访问频率的列表，使用位置列表实现收藏夹列表，按照访问次数来排序"""

    # -------------------------收藏夹类------------------------------
    class _Item:
        """存储访问的元素和访问次数"""
        __slots__ = '_value', '_count'

        def __init__(self, e):
            self._value = e
            self._count = 0

    # ----------------------内部方法-------------------------------
    def find_position(self, e):
        """返回e的位置对象，找不到返回None"""
        current = self._data.first()
        while current is not None and current.element()._value != e:
            current = self._data.after(current)
        return current

    def move_up(self, p):
        """调整位置p按访问次数排列"""
        if p != self._data.first():
            p_count = p.element()._count
            current = self._data.before(p)
            if p_count > current.element()._count:
                while current != self._data.first() and p_count > self._data.before(current).element()._count:
                    current = self._data.before(current)
                self._data.add_before(current, self._data.delete(p))

    # -----------------------外部方法--------------------------------
    def __init__(self):
        self._data = PositionalList()

    def __len__(self):
        return self._data.size

    def __str__(self):
        data = ['head']
        current = self._data.header.next
        for _ in range(len(self)):
            temp_data = str(current.element._value) + ':' + str(current.element._count)
            data.append(temp_data)
            current = current.next
        data.append('tail')
        return str(data)

    def is_empty(self):
        return self._data.size == 0

    def access(self, e):
        """每一次访问便调用此方法"""
        p = self.find_position(e)
        if p is None:
            p = self._data.add_last(self._Item(e))
        p.element()._count += 1
        self.move_up(p)

    def reset_counts(self):
        data_it = iter(self._data)
        for current_p in data_it:
            current_p.element()._count = 0

    def remove(self, e):
        p = self.find_position(e)
        if p is not None:
            self._data.delete(p)

    def clear(self):
        self._data.clear()

    def top(self, k):
        """返回前k个最常访问的收藏夹Item"""
        if not 1 <= k <= self._data.size:
            raise Exception('k数值错误')
        current = self._data.first()
        for _ in range(k):
            item = current.element()
            yield item._value
            current = self._data.after(current)


if __name__ == "__main__":

    F = FavoritesList()
    F.access('A')
    print(F)
    F.remove('A')
    print(F)
    # F.access('baidu')
    # F.access('taobao')
    # F.access('pilipili')
    # F.access('pilipili')
    # F.access('douyu')
    # F.access('douyu')
    # F.access('douyu')
    # F.remove('douyu')
    # for i in F.top(len(F)):
    #     print(i)
    # print(F)
    # F.reset_counts()
    # print(F)